/*
 * @lc app=leetcode.cn id=45 lang=cpp
 *
 * [45] 跳跃游戏 II
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size()==1){return 0;}
        // greedy ??

        // select the most dis(=jumpToIndex+nums[jumpToIndex])
        // in reach of current jump

        int jumpCounter = 0;
        int currentIndex = 0;
        while (1){
            if (currentIndex + nums[currentIndex] >= nums.size()-1){
                return jumpCounter+1;
            }

            int currentJumpDis = nums[currentIndex];

            int maxDis = currentIndex;
            int maxDisIndex = currentIndex;
            for (int i=currentIndex+1;i<=currentIndex+currentJumpDis;i++){
                if (i + nums[i] > maxDis){
                    maxDis = i + nums[i];
                    maxDisIndex = i;
                }
            }

            currentIndex = maxDisIndex;
            jumpCounter += 1;
        }
        return jumpCounter;
    }
};
// @lc code=end

